/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-03
 * Time: 19:22
 */
public class HashArray {
    private static class Node {
        private int key;
        private int value;
        Node next;


        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] arr;
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 8;//默认桶的大小

    public HashArray() {
        this.arr=new Node[10];
    }

    public HashArray(int n){
        this.arr=new Node[n];
    }

    //插入元素
    public int put(int key, int value) {
        int i=key% arr.length;
        Node p=arr[i];
        while(p!=null){
            if(p.key==key){
                int n=p.value;
                p.value=value;
                return n;
            }
            p=p.next;
        }
        Node node=new Node(key,value);
        node.next=arr[i];
        arr[i]=node;
        size++;
        double x=loadFactor();
        if(x>LOAD_FACTOR){
            resize();
        }
        return -1;
    }

    //扩大数组
    private void resize() {
        Node[] brr=new Node[arr.length*2];
        Node p;
        int j;
        for (int i=0;i<arr.length;i++){
            p=arr[i];
            while(p!=null){
                Node p2=p.next;
                j=p.key% brr.length;
                p.next=brr[j];
                brr[j]=p;
                p=p2;
            }
        }
        arr=brr;
    }

    //计算负载因子
    private double loadFactor() {
        return size * 1.0 / arr.length;
    }

    //获取元素
    public int get(int key) {
        int i=key% arr.length;
        Node p=arr[i];
        while(p!=null){
            if(p.key==key){
                return p.value;
            }
            p=p.next;
        }
        return -1;
    }
}
